package com.lml.faceTest;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author luomingliang
 * @date 2021/7/27 19:42
 */
public class Test04 {

    //-------------------------------求斐波那契数列第n项-------------------------------------------------------------
    //0 1 1 2 3 5 8 13 21 ...
    @Test
    public void testFbnq() {
        System.out.println("-----fbnq1-----");
        for (int i = 0; i <= 10; i++)
            System.out.println("第" + i + "项为：" + fbnq1(i));
        System.out.println("-----fbnq2-----");
        for (int i = 0; i <= 10; i++)
            System.out.println("第" + i + "项为：" + fbnq2(i));
        System.out.println("-----fbnq3-----");
        for (int i = 0; i <= 10; i++)
            System.out.println("第" + i + "项为：" + fbnq3(i));
    }

    //求斐波那契数列第n项 递归 复杂度：O(2^n)
    public int fbnq1(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fbnq1(n - 1) + fbnq1(n - 2);
    }

    //求斐波那契数列第n项 去重递归 复杂度：O(n)
    public int recurse(int[] arr, int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (arr[n] != 0) return arr[n];
        arr[n] = recurse(arr, n - 1) + recurse(arr, n - 2);
        return arr[n];
    }

    public int fbnq2(int n) {
        int[] arr = new int[n + 1];
        return recurse(arr, n);
    }

    //复杂度：O(1)
    public int fbnq3(int n) {
        int low = 0, high = 1;
        if (n == 0) return low;
        if (n == 1) return high;
        int target = 0;
        for (int i = 2; i <= n; i++) {
            target = low + high;
            low = high;
            high = target;
        }
        return target;
    }

    //-------------------------------求数组中最大三个数的乘积-------------------------------------------------------------
    @Test
    public void test02() {
        int[] nums = {-7, -8, -9, 1, 5, 3, 7, 10, 9, 2};
        System.out.println(sort(nums));
        System.out.println(getMaxValue(nums));
    }

    /**
     * 分析：
     * 1.如果全是正数或全是负数，则最大值为排序后的最后面三个值的乘积
     * 2.如果正负数都有，且负数个数不少于两个，由于负负得正，最前面两个负数乘积再乘以最后一个数也可能最大
     */
    //求数组中最大三个数的乘积 先排序再比较 复杂度：O(nlogn)
    public static int sort(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        return Math.max(nums[0] * nums[1] * nums[len - 1], nums[len - 1] * nums[len - 2] * nums[len - 3]);
    }

    //线性扫描 先找值 后比较 复杂度：O(n)
    public static int getMaxValue(int[] nums) {
        //min1最小的数，min2第二小的数
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        //max1最大的数，max2第二大的数，max3第三大的数
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }

    //-------------------------------链表反转-------------------------------------------------------------
    @Test
    public void test03() {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);

        ListNode node = recursion(node1);
        System.out.println(node);
    }

    //迭代
    //https://www.bilibili.com/video/BV1Mv411E7Mm?p=59
    public static ListNode iterate(ListNode head) {
        ListNode pre = null, next;
        ListNode curr = head;

        while (curr != null) {
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    //递归
    //https://www.bilibili.com/video/BV1Mv411E7Mm?p=60
    public static ListNode recursion(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode new_head = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return new_head;
    }

    //---------------------------------------环形链表---------------------------------------------------------------

    /**
     *
     */
    @Test
    public void test12() {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);

//        node5.next = node1;
        System.out.println(hasCycle(node1));
        System.out.println(hasCycle2(node1));
    }

    //思路：遍历链表，将遍历过的节点做一个标记，如果之前遇到过，则判定为有环
    //时间：O(n) 空间：O(n)
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

    //思路：双指针法 一个快指针，一个慢指针，遍历时如果有环则必定会相遇。
    //时间：O(n) 空间：O(1)
    public boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head, quick = head.next;
        while (slow != quick) {
            if (quick == null || quick.next == null) {
                return false;
            }
            slow = slow.next;
            quick = quick.next.next;
        }
        return true;
    }

    //-------------------------------求一个正数的平方根(小数）-------------------------------------------------------------
    @Test
    public void test04() {
        System.out.println(sqrt(10, null));
        System.out.println(Math.sqrt(10));
    }

    public static double sqrt(int num, Double precise) {
        if (num < 0)
            throw new IllegalArgumentException("不能传入负数");
        int i = 0;
        for (; i <= num; i++) {
            if (i * i == num) {
                return i;
            }
            if (i * i > num) {
                break;
            }
        }
        double low = i - 1, high = i, pre = precise == null ? 1e-7 : precise;
        double middle = 0;
        while (high - low > pre) {
            middle = (low + high) / 2;
            if (middle * middle > num) {
                high = middle;
            } else {
                low = middle;
            }
        }
        return middle;
    }

    //-------------------------------求一个正数的平方根（整数部分）-------------------------------------------------------------

    /**
     * 在不使用sqrt(x)函数的情况下，得到x的平方根的整数部分
     */
    @Test
    public void test05() {
        System.out.println(sqrtIntegerPart2(24));
    }

    //暴力解法 O(n)
    public int sqrtIntegerPart(int num) {
        if (num <= 1) return num;
        int i = 1;
        for (; i <= num - 1; i++) {
            if (i * i == num) {
                return i;
            }
            if (i * i > num) {
                break;
            }
        }
        return i - 1;
    }

    //logN
    public int sqrtIntegerPart2(int x) {
        int index = -1, low = 0, high = x;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid * mid <= x) {
                index = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return index;
    }

    //----------------------------------------删除排列数组中的重复项-------------------------------------------------------------

    /**
     * 一个有序数组nums，原地删除重复出现的元素，是得每个元素只出现一次，返回删除后数组的长度
     * 不能使用额外的数组空间，必须在原地修改数组并使用O(1)额外空间的条件下完成
     * 例如：输入[0,1,2,2,3,3,4]，输出：5
     */
    @Test
    public void test06() {
        int[] nums = new int[]{0, 1, 2, 2, 3, 3, 4};
        System.out.println(removeDuplicatre1(nums));
        System.out.println(removeDuplicatreMy(nums));
    }

    //双指针法
    public int removeDuplicatre1(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }

    //暴力解法 不符合题目复杂度 my
    //思路：默认个数为数组长度，挨个比较，有相同的个数就减一
    public int removeDuplicatreMy(int[] nums) {
        int length = nums.length;
        if (nums.length == 0) return 0;
        int count = length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                if (nums[i] == nums[j]) {
                    count--;
                }
            }
        }
        return count;
    }

    //---------------------------------------统计素数个数---------------------------------------------------------------
    @Test
    public void test07() {
        System.out.println(countPrimeNumber(100));
        System.out.println(countPrimeNumber(101));
    }

    /**
     * 给定一个数n（n>1）,求2~n之间的素数的个数，例如：输入100，输出25
     */
    //暴力解法
    public int countPrimeNumber(int n) {
        if (n <= 1) return 0;
        int count = 0;
        for (int i = 2; i <= n; i++) {
            boolean isPrime = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                count++;
            }
        }
        return count;
    }

    public int countPrimeNumber2(int n) {
        //TODO

        return 0;
    }

    //-----------------------------------求啤酒瓶数-------------------------------------------------------------------

    /**
     * 50瓶啤酒，3个啤酒空瓶可换一瓶完整的啤酒，问总共可以喝多少瓶
     */
    @Test
    public void test08() {
        System.out.println(countPeer(50) + 50);
        System.out.println(countPeer2(50));
    }

    //总共换多少瓶
    public int countPeer(int num) {
        if (num < 3) return 0;
        return num / 3 + countPeer(num / 3 + num % 3);
    }

    //总共喝多少瓶
    public int countPeer2(int num) {
        int count = num;
        while (num >= 3) {
            num -= 3;
            num++;
            count++;
        }
        return count;
    }

    //---------------------------------------排列硬币---------------------------------------------------------------

    /**
     * 总共有n枚硬币，将它们摆成一个阶梯形状，第k行就必须正好有k枚硬币。
     * 给定一个数字n，找出可形成完整阶梯行的总行数。
     * n是一个非负整数，并且在32位有符号整型的范围内
     */
    @Test
    public void test09() {
        System.out.println(getK(11));
        System.out.println(arrangeCoins(11));
    }

    //k层需要多少硬币
    public int need(int k) {
        if (k == 1) return 1;
        return k + need(k - 1);
    }

    //等差数列的前n项和
    public int need2(int k) {
        return k * (k + 1) / 2;
    }

    //n枚硬币可以盖多少层
    public int getK(int n) {
        //先定义第一层需要的硬币
        int need = 1;
        while ((n = n - need) >= 0) {
            //进入该循环，说明叠加了一层。将下次需要的硬币数计算出来
            need++;
        }
        //未进入循环说明下一层所需的硬币数不够，已经叠好的层数即 need - 1
        return need - 1;
    }

    public int arrangeCoins(int n) {
        for (int i = 1; i <= n; i++) {
            n = n - i;
//            if (n <= i) {
            if (n < i + 1) {
                //进入这里，说明下一次层数的硬币数不够了。已经叠好的层数为i层
                return i;
            }
        }
        return 0;
    }

    public int arrangeCoins2(int n) {

        return 0;
    }

    //---------------------------------------寻找数组的中心下标---------------------------------------------------------------

    /**
     * 给定一个整数数组nums，请编写一个能够返回数组“中心下标”的方法。中心下标是数组的一个下标，
     * 其左侧所有元素相加的和等于右侧所欲元素相加的和。如果数组不存在中心下标，返回-1.如果有多个中心下标，
     * 应该返回最靠近左边的哪一个。
     * 注意：中心下标可能出现在数组的两端
     */
    @Test
    public void test10() {
        System.out.println(findCenterOfArray2(new int[]{1, 7, 3, 6, 5, 6}));
        System.out.println(findCenterOfArray2(new int[]{1, 2, 3, 4, 3, 2, 1}));
        System.out.println(findCenterOfArray2(new int[]{1, 0, 0, 0}));
        System.out.println(findCenterOfArray2(new int[]{1, 0, 0, 1}));
        System.out.println(findCenterOfArray2(new int[]{1, 1, 1, 1}));
    }

    //双指针法 先计算出总和，一个从0开始加，一个从总和开始减，若相等则找到了下标
    public int findCenterOfArray(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
            if (sum == total) {
                return i;
            }
            sum -= nums[i];
        }
        return -1;
    }

    //先计算出总和。从左边开始加，若左边数的和的两倍等于数组总和，则找到下标
    public int findCenterOfArray2(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            if (left * 2 + nums[i] == sum) {
                return i;
            }
            left += nums[i];
        }
        return -1;
    }

    //---------------------------------------两数之和---------------------------------------------------------------

    /**
     * 给定一个整数数组nums，从数组中找出两个数满足相加之和等于目标数target。
     * 假设每个输入只对应唯一的答案，而且不可以重复使用相同元素
     * 返回两数的下标值，以数组形式返回
     */
    @Test
    public void test11() {
        System.out.println(Arrays.toString(solution(new int[]{1, 3, 6, 3, 8}, 9)));
        System.out.println(Arrays.toString(solution(new int[]{1, 3, 6, 3, 8}, 22)));
        System.out.println(Arrays.toString(solution(new int[]{1, 2, 5, 6, 8}, 11)));
        System.out.println(Arrays.toString(solution(new int[]{1, 2, 5, 6, 8}, 22)));
    }

    //暴力解法 时间：O(n^2)
    public int[] solution(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    //用map存储 时间：O(n) 空间：O(n)
    public int[] solution2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) {
                return new int[]{map.get(need), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    //有序数组 例如：{1, 2, 5, 6, 8} 二分法
    public int[] solutionSortArr(int[] nums, int target) {
        //TODO

        return new int[0];
    }

    //有序数组 双指针法
    public int[] twoPoint(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[]{left, right};
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
        return new int[0];
    }
    //---------------------------------------***删除排序数组中的重复项***---------------------------------------------------------------

    /**
     * 一个有序数组nums，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度
     * 不能使用额外的数组空间，必须在原地修改输入数组并在使用O(1)额外空间的条件下完成
     * 例：  输入：[0,1,2,2,3,3,4]
     * 输出：5
     * 重点考察：双指针算法
     */
    @Test
    public void test13() {
        System.out.println(removeDuplicate(new int[]{0, 1, 2, 2, 3, 3, 4}));
        System.out.println(removeDuplicate2(new int[]{0, 1, 2, 2, 3, 3, 4}));
        System.out.println(removeDuplicate3(new int[]{0, 1, 2, 2, 3, 3, 4}));
    }

    //双指针法 i j
    public int removeDuplicate(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }

    //my 暴力解法 想到了使用set集合的特性，但不满足空间O(1)的要求
    public int removeDuplicate2(int[] nums) {
        if (nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        return set.size();
    }

    //my 暴力解法
    public int removeDuplicate3(int[] nums) {
        if (nums.length == 0) return 0;
        int count = nums.length;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                count--;
            }
        }
        return count;
    }

}

class ListNode {
    int value;
    ListNode next;

    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }
}